﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.IsValidSudoku
{
    class MainProject
    {
        static void Main(string[] args)
        {
            //新版生成方式
            //char[,] board = new char[,]
            //{ {  '8', '3', '.', '.', '7', '.', '.', '.', '.' },
            //    {'6','.','.','1','9','5','.','.','.'},
            //    {'.','9','8','.','.','.','.','6','.'},
            //    {'8','.','.','.','6','.','.','.','3'},
            //    {'4','.','.','8','.','3','.','.','1'},
            //    {'7','.','.','.','2','.','.','.','6'},
            //    {'.','6','.','.','.','.','2','8','.'},
            //    {'.','.','.','4','1','9','.','.','5'},
            //    {'.','.','.','.','8','.','.','7','9'}
            //老旧
            char[][] board = new char[][] { new char[] {
                '5', '3', '.', '.', '7', '.', '.', '.', '.' },
              new char[] {'6','.','.','1','9','5','.','.','.'},
              new char[] {'.','9','8','.','.','.','.','6','.'},
              new char[] {'8','.','.','.','6','.','.','.','3'},
              new char[] {'4','.','.','8','.','3','.','.','1'},
              new char[] {'7','.','.','.','2','.','.','.','6'},
              new char[] {'.','6','.','.','.','.','2','8','.'},
              new char[] {'.','.','.','4','1','9','.','.','5'},
              new char[] {'.','.','.','.','8','.','.','7','9'}
            };
            //char[][] board = new char[][] { new char[] {
            //    '5', '3', '.', '.', '7', '.', '.', '.', '.' },
            //  new char[] {'6','.','.','1','9','5','.','.','.'},
            //  new char[] {'.','9','8','.','.','.','.','6','.'},
            //  new char[] {'8','.','.','.','6','.','.','.','3'},
            //  new char[] {'4','.','.','8','.','3','.','.','1'},
            //  new char[] {'7','.','.','.','2','.','.','.','6'},
            //  new char[] {'.','6','.','.','.','.','2','8','.'},
            //  new char[] {'.','.','.','4','1','9','.','.','5'},
            //  new char[] {'.','.','.','.','8','.','.','7','9'}
            //};

            Console.WriteLine(IsValidSudoku(board));

            Console.ReadKey();
        }
        /// <summary>
        /// 位运算方法
        /// </summary>
        /// <param name="board"></param>
        /// <returns></returns>
        public static bool IsValidSudoku(char[][] board)
        {
            int[] horizontal = new int[9];
            int[] vertical = new int[9];
            int[] block = new int[9];
            for (int i = 0; i < board.Length; i++)
            {
                for (int j = 0; j < board[i].Length; j++)
                {
                    if (board[i][j].Equals('.'))
                        continue;

                    int shift = 1 << (board[i][j] - '0');
                    int k = (i / 3) * 3 + j / 3;
                    if ((shift & horizontal[i])>0 || (shift & vertical[j]) > 0 || (shift & block[k]) > 0)
                    {
                        return false;
                    }

                    horizontal[i] |= shift;
                    vertical[j] |= shift;
                    block[k] |= shift;
                }
            }
            return true;
        }

        public static bool IsValidSudoku1(char[][] board)
        {
            HashSet<char> horizontal = new HashSet<char>();
            HashSet<char> vertical = new HashSet<char>();
            HashSet<char> block = new HashSet<char>();

            for (int i = 0; i < board.Length; i++)
            {
                for (int j = 0; j < board[i].Length; j++)
                {
                    if (!board[i][j].Equals('.'))
                    {
                        if (!horizontal.Add(board[i][j]))
                        {
                            return false;
                        }
                    }
                    //横着
                    if (!board[j][i].Equals('.'))
                    {
                        if (!vertical.Add(board[j][i]))
                        {
                            return false;
                        }
                    }
                }
                horizontal.Clear();
                vertical.Clear();

        
                if (i % 3 == 0)
                {
                    for (int k = 0; k < 9; k++)
                    {
                        if (k % 3 == 0)
                            block.Clear();
                        //if (board[i][j].Equals('.'))
                        //    continue;
                        bool isReturn = true;
                        if (!board[i][k].Equals('.'))
                        {
                            isReturn = block.Add(board[i][k]); 
                            if (!isReturn)
                                return isReturn;
                        }
                        if (!board[i+1][k].Equals('.'))
                        {
                            isReturn = block.Add(board[i+1][k]);
                            if (!isReturn)
                                return isReturn;
                        }
                        if (!board[i + 2][k].Equals('.'))
                        {
                            isReturn = block.Add(board[i + 2][k]);
                            if (!isReturn)
                                return isReturn;
                        }
                
                    }
                }
            }
            return true;
            // 00 01 02
            //10 11 12
            //20 21 22
        }
    }
}
